package com.zjw.algorithm;


import java.util.Arrays;

/**
 * 给你一个整数数组 nums，请你将该数组升序排列。
 */
public class Solution22 {

    public static void main(String[] args) {
//        System.out.println(Arrays.toString(new Solution22().sortArray(new int[]{-4, 0, 7, 4, 9, -5, -1, 0, -7, -1})));

        System.out.println("第2题："+Integer.toString(Integer.parseInt("143", 8),10));
    }



    public int[] sortArray(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        qSort(nums, start, end);
        return nums;
    }

    private void qSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        int pl = start;
        int pr = end;
        int pivot = nums[(pl + pr) >> 1];

        while (pl < pr) {
            //find first min
            while (pr > pl && nums[pr] > pivot) {
                pr--;
            }


            while (pl < pr && nums[pl] < pivot) {
                pl++;
            }

            if (nums[pl] == nums[pr]) {
                pl++;
            } else {
                int temp = nums[pl];
                nums[pl] = nums[pr];
                nums[pr] = temp;
            }
        }

        qSort(nums, start, pl - 1);
        qSort(nums, pr + 1, end);
    }
}
